//
// Description: 876. 快速幂求逆元
// Created by Loading on 2022/5/25.
//

/*
 * 若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a（b 能被 a 整除），则存在一个整数 x，使得 a/b ≡ a * x(mod m)，
 * 则称 x 为 b 的模 m 乘法逆元，记为 b^-1 (mod m)。
 *
 * b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^(m−2) 即为 b 的乘法逆元。
 * 证明：a/b = a * b^-1 (mod m)，则 a = a * b * b^-1 (mod m)
 * 推出 b * b^-1 = 1 (mod m)，由费马小定理知，如果 b 和 m 互质，那么 b^(m-1) = 1 (mod m)，
 * 故，b^-1 = b^(m-2)。
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 0x01) {
            res = (LL) res * a % p;
        }
        a = (LL) a * a % p;
        b >>= 1;
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, p;
        cin >> a >> p;

        if (a % p == 0) {
            cout << "impossible" << endl;
        } else {
            cout << qmi(a, p - 2, p) << endl;
        }
    }

    return 0;
}